package dynamicprogramming;

import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 16:30
 */
public class DynamicProgrammingMethod4 extends Example2 {
    @Override
    public void f(int[] items, int[] value, int n, int w) {
        int[] state = new int[w + 1];
        for (int i = 0; i < w + 1; i++) {
            state[i] = -1;
        }

        state[0] = 0;// 第一个之前的状态

        //第一个物品及后面的状态
        for (int i = 0; i < n; i++) {
            for (int j = w - items[i]; j >= 0; j--) {
                if (state[j] >= 0) {
                    state[j + items[i]] = Math.max(state[j + items[i]], state[j] + value[i]);
                }
            }
        }

        // 找出最大的
        for (int i = 0; i < w + 1; i++) {
            maxV = Math.max(state[i], maxV);
        }
    }

    @Test
    public void test() {
        f(items, value, n, w);
        System.out.println(maxV);
    }

}
